#include <iostream>
#include <vector>
#include <limits>
#include <string>
#include <sstream>
#include <fstream>


int mat_mul_order_bottomup ( const std::vector<int> & p, int n, std::vector<std::vector<int> >& m, std::vector<std::vector<int> > & s) {
	for (int i = 0; i < n; i++)
		m[i][i] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			s[i][j] = 0;
	for (int l = 2; l <= n; l++) {
		for (int i = 0; i <= n-l; i++) {
			int q = std::numeric_limits<int>::max();
			for (int k = i; k <= i+l-2; k++) {
				int curr = m[i][k] + m[k+1][i+l-1] + p[i]*p[k+1]*p[i+l];
				if ( q > curr) {
					q = curr;
					s[i][i+l-1] = k;
				}
			}
			m[i][i+l-1] = q;
		}	
	}
	return m[0][n-1];
}

int mat_mul_order_topdown(const std::vector<int> & p, int i, int j, std::vector<std::vector<int> >& m, std::vector<std::vector<int> > & s) {
	if (i >= j)
		return 0;
	if (m[i][j] >0)
		return m[i][j];
	m[i][j] = std::numeric_limits<int>::max();
	for ( int k = i; k < j; k++) {
		int q = mat_mul_order_topdown(p,i,k,m,s) + mat_mul_order_topdown(p,k+1,j,m,s) + p[i]*p[k+1]*p[j+1];
		if ( m[i][j] > q ){
			m[i][j] = q;
			s[i][j] = k;
		}
	}
	return m[i][j];
}

void print_order(const std::vector<std::vector<int> > & s, int i, int j){
	if (i == j)
		std::cout << "A[" << i << ']';
	else {
		std::cout << "(";
		print_order(s,i,s[i][j]);
		print_order(s,s[i][j]+1,j);
		std::cout << ")";
	}
}
void reset(std::vector<std::vector<int> >& m, std::vector<std::vector<int> > & s, int n){
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			m[i][j] = 0;
			s[i][j] = 0;
		}
}

void test_mat_mul_order(){
	int pa[] = {30, 35, 15, 5, 10, 20, 25};
	const std::vector<int> p(pa, pa+sizeof(pa)/sizeof(int));
	int n = sizeof(pa)/sizeof(int) -1;
	std::vector<std::vector<int> > m(n);
	for (int i = 0; i < n; i++)
		m[i].resize(n);
	std::vector<std::vector<int> > s(n);
	for (int i = 0; i < n; i++)
		s[i].resize(n);

	std::cout << "the optimal value(bottom-up) is " << mat_mul_order_bottomup(p,n,m,s) << std::endl;
	print_order(s, 0, n-1); std::cout << std::endl;
	reset(m,s,n);
	std::cout << "the optimal value(top-down) is " << mat_mul_order_topdown(p,0,n-1,m,s) << std::endl;
	print_order(s, 0, n-1); std::cout << std::endl;

	std::string str;
	std::getline(std::cin, str);
	std::stringstream sstr(str);
	std::vector<int> p2;
	int num;
	while (sstr >> num)
		p2.push_back(num);

	reset(m,s,n);
	std::cout << "the optimal value(bottom-up) is " << mat_mul_order_bottomup(p2,n,m,s) << std::endl;
	print_order(s, 0, n-1); std::cout << std::endl;
	reset(m,s,n);
	std::cout << "the optimal value(top-down) is " << mat_mul_order_topdown(p2,0,n-1,m,s) << std::endl;
	print_order(s, 0, n-1); std::cout << std::endl;

}